package leetcode.code1712;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	int mod = (int) 1e9 + 7;

	public int waysToSplit(int[] nums) {
		int len = nums.length;
		int[] presums = new int[len];
		presums[0] = nums[0];
		for (int i = 1; i < len; i++) {
			presums[i] = presums[i - 1] + nums[i];
		}
		int sum = presums[len - 1];
		long ans = 0;
		int L = 1;
		for (int r = 1; r < len - 1; r++) {
			int rsum = sum - presums[r];
			L = this.indexL(L, r, presums, rsum);// (L
			if (L == -1) {
				break;
			}
			int R = this.indexR(L, r, presums, presums[r]);// R]
			if (L <= R) {
				ans += R - L + 1;
				ans %= mod;
			}
		}
		return (int) ans;
	}

	public int indexR(int l, int r, int[] presums, int rsum) {
		if (r < l) {
			return -1;
		}
		int mid = ((r - l) >> 1) + l;
		if (rsum - presums[mid - 1] >= presums[mid - 1]) {
			int ans = mid;
			int ans1 = this.indexR(mid + 1, r, presums, rsum);
			return ans1 > ans ? ans1 : ans;
		} else {
			return this.indexR(l, mid - 1, presums, rsum);
		}
	}

	public int indexL(int L, int r, int[] presums, int target) {
		int sumr = presums[r];
		int ans = -1;
		int l = L;
		while (l >= L && l <= r) {
			int mid = ((r - l) >> 1) + l;
			int sum = sumr - presums[mid - 1];
			if (sum <= target) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		// [3,2,1,1,2,3,4,5,6,7,8,9,0,9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9]
		HelpDebug.compare(3, this.waysToSplit(HelpDebug.str2array3("[3,2,1,1,2,3,4]")));
		HelpDebug.compare(3, this.waysToSplit(HelpDebug.str2array3("[1,2,2,2,5,0]")));
		HelpDebug.compare(3, this.waysToSplit(HelpDebug.str2array3("[1,2,2,2,5,0]")));
		HelpDebug.compare(1, this.waysToSplit(HelpDebug.str2array3("[1,1,1]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
